package leetcode;
import java.util.*;
/**
 * 39.组合总和
 * 给你一个 无重复元素 的整数数组candidates 和一个目标整数target，找出candidates中可以使数字和为目标数target的所有不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
 * candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。对于给定的输入，保证和为target 的不同组合数少于 150 个
 *
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 * 解释：
 * 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
 * 7 也是一个候选， 7 = 7 。
 * 仅有这两种组合。
 *
 * 输入: candidates = [2,3,5], target = 8
 * 输出: [[2,2,2,2],[2,3,3],[3,5]]
 *
 * 输入: candidates = [2], target = 1
 * 输出: []
 */
public class Num_39 {
    List<Integer> inner = new ArrayList<>();
    List<List<Integer>> outter = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates, target, 0, 0);
        return outter;
    }

    //递归函数 (数组，目标值，目前的值，正在遍历的节点)
    private void dfs(int[] candidates, int target, int count, int startIndex) {
        //边界条件
        if(count > target){
            return;
        }else if(count == target){
            outter.add(new ArrayList<>(inner));
            return;
        }

        for (int i = startIndex; i < candidates.length; i++) {
            inner.add(candidates[i]);
            //此时内部递归时，不用startIndex++,因为内部依然可以重复选这个节点
            dfs(candidates, target, count + candidates[i], startIndex);
            inner.remove(inner.size() - 1);
            //当把这个节点弹出后，说明之后的方案不再需要该节点了，所以此时startIndex ++
            startIndex ++;
        }
    }
}
